package com.shm.leetcode;

/**
 * 567. 字符串的排列
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 *
 * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
 *
 * 示例1:
 *
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 *
 *
 * 示例2:
 *
 * 输入: s1= "ab" s2 = "eidboaoo"
 * 输出: False
 *
 *
 * 注意：
 *
 * 输入的字符串只包含小写字母
 * 两个字符串的长度都在 [1, 10,000] 之间
 * @author SHM
 */
public class CheckInclusion {
    /**
     *
     * 方法：双指针（滑动窗口）
     * 这道题是 76. 最小覆盖子串 的简单版本。我们为大家罗列一些要点：
     *
     * 排列不讲究顺序，但是字符出现的 种类 和 次数 要恰好对应相等；
     * 暴力解法做了很多重复和没有必要的工作；
     * 思考可以使用双指针（一前一后、交替向右边移动）的原因：少考虑很多暴力解法须要考虑的子区间，已经得到了一部分子区间的信息以后，很多子区间都不必要考虑，因此根据特定的情况右指针、左指针交替向右移动，从时间复杂度 O(N^2)O(N
     * 2
     *  ) 降到 O(N)O(N)；
     * 由于我们只关心子区间里的元素的种数和各个字符出现的次数。因此须要统计字符串 s1 出现的字符的种数和次数，和在字符串 s2 上的两个变量所确定的滑动窗口中出现的字符种数和次数；
     * 还须要设计一个变量 winCount，表示滑动窗口在 s2 上滑动的时候，出现在 s1 中的字符的种类数，规则如下：
     * 如果某一个字符出现的次数恰好等于 s1 中对应字符出现的次数，winCount += 1；
     * 在左边界向右移动的过程当中，某一个字符对应的次数减少以后，恰好小于了 s1 对应的字符出现的次数，winCount -= 1；
     * 当滑动窗口中出现的字符种类数和 s1 中出现的字符种类数相等（根据 winCount 的定义，对应次数也相等），并且 s2 上的滑动窗口的长度等于字符串 s1 的长度的时候，就找到了 s1 的一个排列。
     * 注意：请大家特别留意 winCount 的含义：滑动窗口中的字符要满足字符出现的次数 大于等于 s1 中对应字符出现的次数的时候才加 11，winCount 不仅统计了种类，还代表了次数。使得我们可以通过 winCount 的数值去了解整个滑动窗口的信息。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(|s1|+|s2|)O(∣s1∣+∣s2∣)，这里 |s1|∣s1∣ 表示字符串 s1 的长度，这里 |s2|∣s2∣ 表示字符串 s2 的长度；
     * 空间复杂度：O(|\Sigma|)O(∣Σ∣)，这里 \SigmaΣ 表示字符集，即 s1 和 s2 中出现的所有的字符，|\Sigma|∣Σ∣ 是字符集的大小，取决于出现字符的最小 ASCII 值和最大 ASCII 值。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-q6tp/
     * @param s1
     * @param s2
     * @return
     */
    public boolean checkInclusion(String s1, String s2) {
        int pLen = s1.length();
        int tLen = s2.length();
        char[] pattern = s1.toCharArray();
        char[] text = s2.toCharArray();
        int left = 0,right= 0;
        int[] freq = new int[26];
        int[] win = new int[26];
        int pCount = 0,winCount = 0;

        for (char c : pattern) {
            freq[c-'a']++;
        }

        for (int i : freq) {
            if(i>0){
                pCount++;
            }
        }
        //// 当滑动窗口中的某个字符个数与 s1 中对应相等的时候才计数
        while (right<tLen){
            if(freq[text[right]-'a']>0){
                win[text[right]-'a']++;
                if (freq[text[right]-'a']==win[text[right]-'a']){
                    winCount++;
                }
            }
            right++;
            while (pCount==winCount){
                //当滑动窗口中出现的字符种类数和 s1 中出现的字符种类数相等（根据 winCount 的定义，对应次数也相等），并且 s2 上的滑动窗口的长度等于字符串 s1 的长度的时候，就找到了 s1 的一个排列。
                if(right-left==pLen){
                    return true;
                }
                if(freq[text[left]-'a']>0){
                    win[text[left]-'a']--;
                    if(win[text[left]-'a']<freq[text[left]-'a']){
                        winCount--;
                    }
                }
                left++;
            }
        }
        return false;
    }
}
